#include <vector>
#include <unordered_map>
#include <string>
using namespace std;


// version 1
class Solution {
public:
//version 1 先不掠过不存在子串
    vector<int> findSubstring(string s, vector<string>& words) {
        int step = words[0].size(), line = step * words.size();
        //前者为一个单词长度，后者为一个串联子串的长度

        //经过分析，是需要进行step次滑动窗口的过程的。每一次的开头都是向后移动一个字符(第一次从第一个字母开始)
        //这样做的原因是，很有可能会出现一种情况：我们按照step取子串的时候，发现可能会把正确的子串给拆分了
        //但是，为什么只需要进行step次呢？因为后序的都是和前面有重叠的！后面有答案的话，前面也是一定计算到的，再进行计算就重复了

        //这题的原理就类似于Leetcode_438，只不过把字符变成子串罢了。为了方便使用，我们使用STL的容器来进行辅助。
        //再使用数组就太麻烦了

        
        int useful_str_num = 0;                    //统计有效子串数据，这是为了简化哈希表比较相等的逻辑，优化
        vector<int> ret;                           //返回结果
        int slide_times = 0;                       //滑动窗口执行次数
        unordered_map<string, int> _words_count;   //统计传入数组words的子串情况  

        //先行统计words的情况
        for (auto& str : words) _words_count[str]++; 


        while (slide_times < step) {
            //这两句必须放在里面写，因为这是每一次滑动窗口都要用的！要不然在外面写需要手动清空
            unordered_map<string, int> _Windows_count; //统计窗口中的子串的情况
            int useful_str_num = 0;                    //统计有效子串数据，这是为了简化哈希表比较相等的逻辑，优化 
            
            for (int left = slide_times, right = slide_times; right < s.size(); right += step) {
                string input_substr = s.substr(right, step); //取出从right开始长度为step的子串
                if (input_substr.size() < step) break; //能取不出那么长度子串

                //TODO 可能会出现不存在的子串，可以进一步优化

                //入窗口前，需要调整有效子串个数
                if (_Windows_count[input_substr] < _words_count[input_substr]) ++useful_str_num;
                //入窗口
                _Windows_count[input_substr]++;

                if (right - left + step == line) {
                    //窗口长度达标 -> 判断一下窗口哈希表和words哈希表是否相同
                    if (useful_str_num == words.size())
                        ret.push_back(left);//有效数据一样！

                    //出窗口前，需要调整有效子串个数
                    string output_substr = s.substr(left, step);

                    //这里要注意细节，就是说如果不存在的子串入了窗口，就不要操作useful_str_num，会出错
                    //因为没有掠过不存在的子串
                    if (_Windows_count[output_substr] <= _words_count[output_substr] 
                    && _words_count[output_substr] != 0) --useful_str_num;

                    //出窗口
                    _Windows_count[output_substr]--;
                    left += step;
                }
            }
            ++slide_times;
        }

        return ret;
    }
};



//version 2
class Solution {
public:
//version 2 只要碰到了不存在于words中的子串，直接掠过
    vector<int> findSubstring(string s, vector<string>& words) {
        int step = words[0].size(), line = step * words.size();
        //前者为一个单词长度，后者为一个串联子串的长度

        //经过分析，是需要进行step次滑动窗口的过程的。每一次的开头都是向后移动一个字符(第一次从第一个字母开始)
        //这样做的原因是，很有可能会出现一种情况：我们按照step取子串的时候，发现可能会把正确的子串给拆分了
        //但是，为什么只需要进行step次呢？因为后序的都是和前面有重叠的！后面有答案的话，前面也是一定计算到的，再进行计算就重复了

        //这题的原理就类似于Leetcode_438，只不过把字符变成子串罢了。为了方便使用，我们使用STL的容器来进行辅助。
        //再使用数组就太麻烦了

        
        int useful_str_num = 0;                    //统计有效子串数据，这是为了简化哈希表比较相等的逻辑，优化
        vector<int> ret;                           //返回结果
        int slide_times = 0;                       //滑动窗口执行次数
        unordered_map<string, int> _words_count;   //统计传入数组words的子串情况  

        //先行统计words的情况
        for (auto& str : words) _words_count[str]++; 


        while (slide_times < step) {
            //这两句必须放在里面写，因为这是每一次滑动窗口都要用的！要不然在外面写需要手动清空
            unordered_map<string, int> _Windows_count; //统计窗口中的子串的情况
            int useful_str_num = 0;                    //统计有效子串数据，这是为了简化哈希表比较相等的逻辑，优化 
            
            for (int left = slide_times, right = slide_times; right < s.size(); right += step) {
                string input_substr = s.substr(right, step); //取出从right开始长度为step的子串
                if (input_substr.size() < step) break; //可能取不出那么长度子串

                //可能会出现不存在的子串，可以进一步优化
                //if(_words_count[input_substr] == 0){
                if(_words_count.count(input_substr) == 0){  //改成这一句 时间复杂度大大降低！
                    //直接清空窗口
                    _Windows_count.clear();
                    //有效数据清零
                    useful_str_num = 0;
                    left = right + step;
                    continue;
                }

                //入窗口前，需要调整有效子串个数
                if (_Windows_count[input_substr] < _words_count[input_substr]) ++useful_str_num;
                //入窗口(此时子串一定是在words中找得到的)
                _Windows_count[input_substr]++;

                if (right - left + step == line) {
                    //窗口长度达标 -> 判断一下窗口哈希表和words哈希表是否相同
                    if (useful_str_num == words.size())
                        ret.push_back(left);//有效数据一样！

                    //出窗口前，需要调整有效子串个数
                    string output_substr = s.substr(left, step);
                    if (_Windows_count[output_substr] <= _words_count[output_substr]) --useful_str_num;

                    //出窗口
                    _Windows_count[output_substr]--;
                    left += step;
                }
            }
            ++slide_times;
        }

        return ret;
    }
};